package org.example.interview;

import java.util.Arrays;
import java.util.Random;

public class Demo {
    public static void main(String[] args) {
        int[] arr = {2,3,1,4,5,8,2,3,11};
        Demo demo = new Demo();
        demo.quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            int pivot = partition(arr, start, end);
            quickSort(arr, start, pivot-1);
            quickSort(arr, pivot+1, end);
        }
    }

    private int partition(int[] arr, int start, int end) {
        int random = new Random().nextInt(end-start+1) + start;
        swap(arr, start, random);
        int compare = arr[start];
        int cursor = start;
        for (int i=start+1;i<=end;i++) {
            if (arr[i] < compare) {
                cursor++;
                swap(arr, cursor, i);
            }
        }
        swap(arr, cursor, start);
        return cursor;
    }

    private void swap(int[] arr, int from , int to) {
        int temp = arr[from];
        arr[from] = arr[to];
        arr[to] = temp;
    }
}
